package A.动态数组;

import java.util.Map;

/**
 * 给你两个数组，arr1 和 arr2，
 *
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _1122_数组的相对排序 {
    /**
     * 直接看题解：
     * 首先需要获得arr1的最大数 用来最终遍历
     * 需要一个数组来进行arr1数组的计数 index为数值 对应的数值为出现的次数；
     * 之后利用arr2进行一次遍历 以对应的数值在计数数组的结果作为循环条件 将其输出在arr1数组中
     * 最后arr2遍历结束之后，从0开始到max 只要计数数组对应的值>0 就arr1输出 并且计数数组值-1
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {


        int max = Integer.MIN_VALUE;
        for (int num:arr1){
            max = Math.max(max,num);//获得最大值
        }

        int[] bucket = new int[max+1];
        for (int num:arr1){
            bucket[num]++;  //构建计数数组
        }


        int i=0;
        for (int num:arr2){
            for (int j=0;j<bucket[num];j++){
                arr1[i++] = num;//全局i 用来arr1输出 如果用j 每次都是从0开始
            }
            bucket[num] =0;//记得遍历完之后给清零 否则arr1就越界输出了
        }

        for (int p=0;p<=max;p++){
            while ( bucket[p]>0){
                arr1[i++] =p;
                bucket[p]--;
            }
        }

        return  arr1;



    }




    }
